package com.dragon.datastructure.search;

/**
 * 插值查找算法
 * 对于数据量较大，关键字分布比较均匀的查找表来说，采用插值查找, 速度较快.
 * 关键字分布不均匀的情况下，该方法不一定比折半查找要好
 *
 * @author dragon
 * @since 2019/12/26
 */
public class InsertValueSearch {


    public static void main(String[] args) {
        int[] array = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20};
        int i = binarySearch(array, 0, array.length - 1, 1);
        System.out.println(i);
    }

    public static int binarySearch(int[] array, int left, int right, int findValue) {
        System.out.println("hello!");
        if (left > right || findValue < array[0] || findValue > array[array.length - 1]) {
            return -1;
        }

        // 求出mid, 自适应
        int mid = left + (right - left) * (findValue - array[left]) / (array[right] - array[left]);
        if (findValue < array[mid]) {
            return binarySearch(array, left, mid - 1, findValue);
        } else if (findValue > array[mid]) {
            return binarySearch(array, mid + 1, right, findValue);
        } else {
            return mid;
        }

    }
}
